Rank transform of an array

Time: O(NLogN); Space: O(N); easy

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules: * Rank is an integer starting from 1. * The larger the element, the larger the rank. If two elements are equal, their rank must be the same. * Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]

Output: [4,1,2,3]

Explanation:

  • is the largest element.

  • is the smallest.

  • is the second smallest.

  • is the third smallest.

Example 2:

Input: arr = [100,100,100]

Output: [1,1,1]

Explanation:

  • Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]

Output: [5,3,4,2,8,6,7,1,3]

Notes:

  • 0 <= len(arr) <= 105

  • -109 <= arr[i] <= 109

Hints:

  1. Use a temporary array to copy the array and sort it.

  2. The rank of each element is the number of elements smaller than it in the sorted array plus one.

[3]:

class Solution1(object):
    def arrayRankTransform(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        return list(map({x: i+1 for i, x in enumerate(sorted(set(arr)))}.get, arr))

[4]:

s = Solution1()
arr = [40,10,20,30]
assert s.arrayRankTransform(arr) == [4,1,2,3]
arr = [100,100,100]
assert s.arrayRankTransform(arr) == [1,1,1]
arr = [37,12,28,9,100,56,80,5,12]
assert s.arrayRankTransform(arr) == [5,3,4,2,8,6,7,1,3]